package com.bee.剑指offer;

/**
 * 统计一个数字在排序数组中出现的次数。
 */
public class 在排序数组中查找数字 {

    /**
     * 使用二分查找，找到了该元素，不返回，在去遍历左右附近的重复的元素，数组是有序的才能使用二分查找
     */
    public static int search (int[] nums, int target) {
        int count = 0;
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high)/2;
            if(nums[mid] == target) {
                count++;
                for (int i = mid - 1;(i >=0)&&(i < mid); i--) {
                    if(nums[i] != target) {
                        break;
                    }
                    count++;
                }
                for (int i = mid + 1;(i < nums.length); i++) {
                    if(nums[i] != target) {
                        break;
                    }
                    count++;
                }
                return count;
            }
            if(nums[mid] < target) {
                low = mid + 1;
            }
            if (nums[mid] > target) {
                high = mid - 1;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int search = search(new int[]{5, 7, 7, 8, 8, 10}, 8);
        System.out.println(search);
    }
}
